#pragma once

#include "allocator.hpp"
#include "functor.hpp"
#include "algo_meta_func.hpp"
#include "pair.hpp"
#include "rbtree.hpp"

namespace zuck
{
	template<
		bool multi, typename Valty, 
		typename _Cmp, typename _Equal, typename Alloc>
	class UMap_Traits {
	public:
		using key_type		 = Valty;
		using value_type	 = Valty;
		using key_compare	 = _Cmp;
		using equal			 = _Equal;
		using allocator_type = Alloc;

		static bool constexpr _Multi = multi;
	};

	template<typename T, 
		typename _Cmp   = zuck::less<T>,
		typename _Equal = zuck::equal_to<T>,
		typename Alloc = zuck::allocator<T>
	>
	class set : public _rbtree<UMap_Traits<false, T, _Cmp, _Equal, Alloc>>
	{
	private:
		using _Base		= _rbtree<UMap_Traits<false, T, _Cmp, _Equal, Alloc>>;
		using _Node_ptr = __tree_node<false, T>*;
	public:
		using value_type		= typename _Base::value_type;
		using size_type			= typename _Base::size_type;
		using pointer			= typename _Base::pointer;
		using reference			= typename _Base::reference;
		using const_reference	= typename _Base::const_reference;
		using rvalue_reference	= typename _Base::rvalue_reference;
	public:
		using iterator				 = typename _Base::iterator;
		using const_iterator		 = typename _Base::const_iterator;
		using reverse_iterator		 = typename _Base::reverse_iterator;
		using const_reverse_iterator = typename _Base::const_reverse_iterator;
	public:
		set()noexcept : _Base() {}

		set(std::initializer_list<T> data) : _Base(data) {}

		set(std::initializer_list<T> data, Alloc al) : _Base(data, al) {}

		template<typename PointerType, 
			zuck::enable_if_t<zuck::is_iterator_v<PointerType>, int> = 0>
		set(PointerType Begin, PointerType End) : _Base(Begin, End) {}
		
		template<typename PointerType, 
			zuck::enable_if_t<zuck::is_iterator_v<PointerType>, int> = 0>
		set(PointerType Begin, PointerType End, Alloc al) : _Base(Begin, End, al) {}

		set(set const& other, _Cmp const& _pr) : _Base(other, _pr) {}

		set(set const& other) : _Base(other) {}

		set(set&& other)noexcept : _Base(zuck::move(other)) {}

		size_type count(T const& val)const
		{ return (find(val) == nir<false, T>) ? 0 : 1; }

		size_type count(T&& val)
		{ return (find(val) == nir<false, T>) ? 0 : 1; }

		template<typename...Args>
		pair<iterator, bool> try_emplace(Args&&...args)
		{
			auto _Iter = __find_node(T(zuck::forward<Args>(args)...));
			if (_Iter) {
				return { _Iter, false };
			}
			return __insert_aux(T(zuck::forward<Args>(args)...));
		}

		template<typename...Args>
		inline T& emplace(Args&&... args)
		{ return *(__insert_aux(T(zuck::forward<Args>(args)...)).first); }

		size_type erase(const T& val)
		{
			if (__find_node(val) == iterator(nir<false, T>)) {
				return 0;
			}
			_Base::_m_root = __remove_node(_Base::_m_root, val);
			_Base::_m_root->__col = _Color::black;
			return 1;
		}

		size_type erase(T&& val)
		{
			if (__find_node(val) == iterator(nir<false, T>)) {
				return 0;
			}
			_Base::_m_root = __remove_node(_Base::_m_root, val);
			_Base::_m_root->__col = _Color::black;
			return 1;
		}

		inline set& operator=(set const& other)
		{
			_Base::operator=(other);
			return *this;
		}

		inline set& operator=(set&& other)noexcept
		{
			_Base::operator=(zuck::move(other));
			return *this;
		}

	private:
		pair<iterator, bool> __insert_aux(T const& val)
		{
			_Base::_m_root = _Base::__insert(nir<false, T>, _Base::_m_root, val);
			_Base::_m_root->__col = _Color::black;
			_Base::_m_root->_m_p   = nir<false, T>;
			nir<false, T>->__l   = _Base::_m_root;

			return _Base::__exist ? pair<iterator, bool>(nil<false, T>, !_Base::__exist) :
				pair<iterator, bool>(__find_node(val), !_Base::__exist);
		}

		__tree_node<false, value_type>* __remove_node(_Node_ptr root, value_type const& val)
		{
			if (root == nil<false, value_type>) {
				iterator{ nir<false, T>, _Base::_Max() };
			}
			if (__cmp(val, *(root->__d))) {
				root->__l = __remove_node(root->__l, val);
			}
			else if (__cmp(*(root->__d), val)) {
				root->__r = __remove_node(root->__r, val);
			}
			else {
				if (root->__l == nil<false, value_type> || root->__r == nil<false, value_type>) {
					_Node_ptr tmp = ((root->__l == nil<false, value_type>) ? root->__r : root->__l);
					_Base::alloc.deallocate(root, 1);
					--_Base::_m_cnt;
					return tmp;
				}
				else {
					_Node_ptr _pre = _Base::__predecessor(root);
					root->__d = _pre->__d;
					root->__l = __remove_node(root->__l, _pre->__d);
				}
			}
			return _Base::__remove_balance(root);
		}
	};


// class template parameter deduction needs C++ 17 standard support !
	template<typename T,
		typename _Cmp	= zuck::less<T>,
		typename _Equal = zuck::equal_to<T>,
		typename Alloc = zuck::allocator<T>>
	set(std::initializer_list<T>)->set<T, _Cmp, _Equal, Alloc>;

	template<typename T,
		typename _Cmp = zuck::less<T>,
		typename _Equal = zuck::equal_to<T>,
		typename Alloc = zuck::allocator<T>>
	set(std::initializer_list<T>, Alloc)->set<T, _Cmp, _Equal, Alloc>;

	template<typename PointerType,
		typename T,
		typename _Cmp	= zuck::less<T>,
		typename _Equal = zuck::equal_to<T>,
		typename Alloc = zuck::allocator<T>>
	set(PointerType, PointerType)->set<T, _Cmp, _Equal, Alloc>;

	template<typename PointerType,
		typename T,
		typename _Cmp = less<T>,
		typename _Equal = zuck::equal_to<T>,
		typename Alloc = zuck::allocator<T>>
	set(PointerType, PointerType, Alloc)->set<T, _Cmp, _Equal, Alloc>;

	template<typename T, 
		typename _Cmp	= less<T>, 
		typename _Equal = zuck::equal_to<T>, 
		typename Alloc = zuck::allocator<T>>
	set(set<T> const&)->set<T, _Cmp, _Equal, Alloc>;

	template<typename T, 
		typename _Cmp	= less<T>, 
		typename _Equal = zuck::equal_to<T>, 
		typename Alloc = zuck::allocator<T>>
	set(set<T>&&)->set<T, _Cmp, _Equal, Alloc>;
}

